#pragma once
#include <iostream>
#include <assert.h>

using namespace std;

class Node
{
public:
	int data;
	Node* next;
	Node(int x)
	{
		data = x;
		next = nullptr;
	}
};

class Queue
{
public:
	Queue()
	{
		head = nullptr;
		size = 0;
	}
	void Print()
	{
		Node* cur = head;
		while (cur)
		{
			cout << cur->data << " ";
			cur = cur->next;
		}
		cout << endl;
	}
	Node* CreateNode(int x)
	{
		Node* newnode = new Node(x);
		return newnode;
	}
	void Push(int x)
	{
		Node* newnode = CreateNode(x);
		Node* tail = head;
		if (tail == nullptr) tail = head = newnode;
		else
		{
			while (tail->next)
			{
				tail = tail->next;
			}
			tail->next = newnode;
		}
		size++;
	}
	void Pop()
	{
		assert(size > 0);
		Node* first = head->next;
		delete head;
		head = first;
		size--;
	}

	void Delete()
	{
		Node* cur = head;
		while (cur)
		{
			Node* next = cur->next;
			delete cur;
			cur = next;
		}
		head = nullptr;
		size = 0;
	}
	int Front()
	{
		return head->data;
	}
	int Back()
	{
		Node* tail = head;
		while (tail->next)
		{
			tail = tail->next;
		}
		return tail->data;
	}
	int Size()
	{
		return size;
	}
	bool Empty()
	{
		return size == 0;
	}

	~Queue()
	{
		Delete();
	}
private:
	Node* head;
	int size;
};